package com.longge;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-05-03 03:14
 */
public class SlidingPuzzle {

    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        HashSet<String> visited = new HashSet<>();
        LinkedList<String> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int[] aBoard : board) {
            for (int anABoard : aBoard) {
                sb.append((char) (anABoard + '0'));
            }
        }
        visited.add(sb.toString());
        queue.offer(sb.toString());
        int count = 0;

        int[][] neighbor = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(target)) return count;
                int j = 0;
                for (; cur.charAt(j) != '0'; j++) ;
                for (int n : neighbor[j]) {
                    String newStr = swap(cur, j, n);
                    if (!visited.contains(newStr)) {
                        visited.add(newStr);
                        queue.offer(newStr);
                    }
                }
            }
            count++;
        }
        return -1;
    }

    private String swap(String cur, int j, int n) {
        char[] chars = cur.toCharArray();
        char temp = chars[j];
        chars[j] = chars[n];
        chars[n] = temp;
        return new String(chars);
    }

    public static void main(String[] args) {
        new SlidingPuzzle().slidingPuzzle(new int[][]{{1,2,3},{4,0,5}});
    }
}
